/*
--------------------------------------------------------------------------------
				Ak-Lib. 
			 Project       	: Ak-Lib
			 Group         	: Ak-Lib R&D Team
			 Author        	: Ocean.Wang
			 Create Date 	: 05-01-2010
--------------------------------------------------------------------------------
Code Name 	:  A.K 	~v~
Description	:  Yet Another Cross-Platform Lib.
Cautions    	:
--------------------------------------------------------------------------------
Change History:
Version		: 0.1
Building 		: 05/01/10
10-05.01 first draft, build, debug and test.
--------------------------------------------------------------------------------
*/

#ifndef _INC_AK_TREE_
#define	_INC_AK_TREE_

#include "ak_queue.h"

#ifdef __cplusplus
extern "C" {
#endif

/* Marco Here Used by the Judgement CallBack */
#define _TREE_LESS 		-1
#define _TREE_EQUAL 	0
#define _TREE_GREAT 	1


/* -----------------------------------------------------------------------------
** Red - Black Tree.
** 
*/
/* Linux */
#if 	_TARGET_OS == _OS_GNU
typedef struct _t_rbnode{
	unsigned long long 	rb_pcolor;
	struct _t_rbnode *	rb_right;
	struct _t_rbnode *	rb_left;
}_t_rbnode _OS_ALIGN(sizeof(long long));

typedef struct  _t_rbroot{
	struct _t_rbnode * rb_node;
}_t_rbroot;

/* Windows */
#elif 	_TARGET_OS == _OS_WIN
typedef _OS_ALIGN(8) struct  _t_rbnode{
	unsigned long long 	rb_pcolor;
	struct _t_rbnode *	rb_right;
	struct _t_rbnode *	rb_left;
}_t_rbnode;

typedef struct  _t_rbroot{
	struct _t_rbnode * rb_node;
}_t_rbroot;

#endif


static __inline void rb_set_parent(_t_rbnode *rNode, _t_rbnode *p)
{
	rNode->rb_pcolor = (rNode->rb_pcolor & 3) | (unsigned long long)(unsigned long)(p);
}

#define RB_CLEAR_ROOT(rRoot)		((rRoot)->rb_node = NULL)
#define RB_CLEAR_NODE(rNode)		(rb_set_parent(rNode, rNode))


/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern 	void 			rb_replace(_t_rbroot *rRoot, _t_rbnode *rOld, _t_rbnode *rNew);
extern 	void 			rb_erase(_t_rbroot *rRoot,  _t_rbnode *rNode);

extern _t_rbnode *		rb_next(_t_rbnode * rNode);
extern _t_rbnode *		rb_prev(_t_rbnode * rNode);

extern _t_rbnode *		rb_first(_t_rbroot * rRoot);
extern _t_rbnode *		rb_last(_t_rbroot * rRoot);

extern 	_t_rbnode * 	rb_find(_t_rbroot * rRoot, _t_rbnode * rNode,  int (*fCmp)());
extern	_t_rbnode * 	rb_insert(_t_rbroot * rRoot, _t_rbnode * rNode, int (*fCmp)());


#ifdef __cplusplus
}
#endif

#endif


